ABC145 C - Average Length
問題文
問題文座標平面上に $ N 個の町があります。町 $ i は、座標 ( $ x_i , $ y_i ) に位置しています。町 $ i と町 $ j の間の距離は $ \sqrt{\left(x_i-x_j\right)^2+\left(y_i-y_j\right)^2} です。
これらの町を全て $ 1 回ずつ訪れるとき、町を訪れる経路は全部で $ N! 通りあります。$ 1 番目に訪れる町から出発し、$ 2 番目に訪れる町、$ 3 番目に訪れる町、$ \ldots 、を経由し、$ N 番目に訪れる町に到着するまでの移動距離 (町から町への移動は直線移動とします) を、その経路の長さとします。これらの $ N! 通りの経路の長さの平均値を計算してください。
制約
$ 2 ≤ N ≤ 8
$ -1000 ≤ x_i ≤ 1000
$ -1000 ≤ y_i ≤ 1000
$ \left(x_i, y_i\right) \neq \left(x_j, y_j\right) ( $ i \neq j のとき)
(21:12 追記) 入力中の値はすべて整数である。
入力
入力入力は以下の形式で標準入力から与えられる。
$ N
$ x_1 $ y_1
$ :
$ x_N $ y_N
出力
経路の長さの平均値を出力せよ。
出力は、ジャッジの出力との絶対誤差または相対誤差が $ 10^{-6} 以下のとき正解と判定される。
入力例 1
code:memo
3
0 0
1 0
0 1
出力例 1
code:memo
2.2761423749
町を訪れる経路は $ 1 → $ 2 → $ 3 , $ 1 → $ 3 → $ 2 , $ 2 → $ 1 → $ 3 , $ 2 → $ 3 → $ 1 , $ 3 → $ 1 → $ 2 , $ 3 → $ 2 → $ 1 の $ 6 通りです。
このうち、経路 $ 1 → $ 2 → $ 3 の長さは、$ \sqrt{\left(0-1\right)^2+\left(0-0\right)^2} + \sqrt{\left(1-0\right)^2+\left(0-1\right)^2} = 1+\sqrt{2} となります。
同様に他の経路についても長さを計算すると、経路の長さの平均値は、
$ \frac{\left(1+\sqrt{2}\right)+\left(1+\sqrt{2}\right)+\left(2\right)+\left(1+\sqrt{2}\right)+\left(2\right)+\left(1+\sqrt{2}\right)}{6} = 2.276142...
であると分かります。
入力例 2
code:memo
2
-879 981
-866 890
出力例 2
code:memo
91.9238815543
町を訪れる経路は $ 1 → $ 2 , $ 2 → $ 1 の $ 2 通りありますが、これらの経路の長さは一致します。
入力例 3
code:memo
8
-406 10
512 859
494 362
-955 -475
128 553
-986 -885
763 77
449 310
出力例 3
code:memo
7641.9817824387
Java回答
code:main.java
import java.util.Scanner;
public class Main {
public static double dist(int[] arr1, int[] arr2) {
double res = (arr10 - arr20)*(arr10 - arr20) + (arr11 - arr21)*(arr11 - arr21); return Math.sqrt(res);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
// String S = in.next();
int dist[][] = new intN2; for (int i = 0; i < N; i++) {
}
double ans = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
ans += dist(disti, distj); }
}
System.out.println(String.format("%.07f", ans/N));
}
}